package com.liang.leetcode.binarytree.util;

import com.liang.leetcode.binarytree.entity.TreeNode;

import java.util.*;

/**
 * 二叉树工具类
 */
public class BiTreeUtil {
    public static void main(String[] args) {
        List<Integer> nodes = Arrays.asList(1, 2, 3, null, null, 4, null, null, null, null, null, 1, 1);
        TreeNode root = createBiTreeByRecursion(nodes);
        // TreeNode root = createBiTreeByLevel(nodes);
        List<Integer> result = preorderTraversal(root);
        System.out.println(result);
    }

    /**
     * 递归创建二叉树，返回根节点
     * 通过重载函数，将 index 的默认值设为 0，统一调用方式
     */
    public static TreeNode createBiTreeByRecursion(List<Integer> nodeList) {
        return createBiTreeByRecursion(nodeList, 0);
    }

    /**
     * 递归创建二叉树：根据二叉树的顺序存储数组创建二叉树
     * 举例：Integer[] nodes = {1, 2, 4, 3, null, 5, 6}; 相当于二叉树层序遍历顺序，空节点为 null，要补全所有层的 null 节点，不然子树节点索引会计算错误
     * 则创建的二叉树先序遍历为：1 2 3 4 5 6
     * @param nodeList 二叉树的顺序存储数组
     * @param index 当前节点在数组中的索引
     * @return 返回创建的二叉树的根节点
     */
    public static TreeNode createBiTreeByRecursion(List<Integer> nodeList, int index) {
        // 退出条件为节点值为 null 或者超出列表范围
        if (index >= nodeList.size() || nodeList.get(index) == null) {
            return null;
        }
        // 创建的新节点
        TreeNode root = new TreeNode(nodeList.get(index));
        // 递归创建左子树，索引计算为当前索引的两倍加一
        root.left = createBiTreeByRecursion(nodeList, 2 * index + 1);
        // 递归创建右子树，索引计算为当前索引的两倍加二
        root.right = createBiTreeByRecursion(nodeList, 2 * index + 2);
        return root;
    }

    /**
     * 迭代创建二叉树
     * 按照层序遍历的顺序从列表中取值创建二叉树
     * @param nodeList 包含树节点值的整数列表，null元素表示不存在的节点
     * @return 树的根节点
     */
    public static TreeNode createBiTreeByLevel(List<Integer> nodeList) {
        if (nodeList == null || nodeList.isEmpty()) {
            return null;
        }
        // 创建根节点
        TreeNode root = new TreeNode(nodeList.get(0));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1;
        while (!queue.isEmpty() && index < nodeList.size()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 出队当前节点，再创建左右孩子节点
                TreeNode node = queue.poll();
                if (index < nodeList.size() && nodeList.get(index) != null) {
                    node.left = new TreeNode(nodeList.get(index));
                    queue.offer(node.left);
                }
                index++;
                if (index < nodeList.size() && nodeList.get(index) != null) {
                    node.right = new TreeNode(nodeList.get(index));
                    queue.offer(node.right);
                }
                index++;
            }
        }
        return root;
    }

    // 先序遍历二叉树
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderTraversal(root, result);
        return result;
    }

    public static void preorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorderTraversal(root.left, result);
        preorderTraversal(root.right, result);
    }

    // 层序遍历二叉树
    public static List<List<Integer>> levelTraversal(TreeNode root) {
        // 存储层次遍历结果的列表
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        // 将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 存储当前层的遍历结果
            List<Integer> levelList = new ArrayList<>();
            // 获取当前层的节点数量
            int size = queue.size();
            // 遍历当前层节点，再把下一层节点入队
            for (int i = 0; i < size; i++) {
                // 出队当前节点，放入当前层的列表中
                TreeNode node = queue.poll();
                assert node != null;
                levelList.add(node.val);
                // 如果当前节点的左子节点不为空，将其入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                // 如果当前节点的右子节点不为空，将其入队
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 保存当前层节点遍历结果
            resultList.add(levelList);
        }
        // 返回层次遍历的结果
        return resultList;
    }
}
